package leetcode.editor.cn.dsa28_apply;
//如果可以通过将 A 中的两个小写字母精确地交换位置 K 次得到与 B 相等的字符串，我们称字符串 A 和 B 的相似度为 K（K 为非负整数）。
// 给定两个字母异位词 A 和 B ，返回 A 和 B 的相似度 K 的最小值。
//
// 示例 1：
// 输入：A = "ab", B = "ba"
//输出：1
// 
// 示例 2：
// 输入：A = "abc", B = "bca"
//输出：2
//
// 示例 3： 
// 输入：A = "abac", B = "baca"
//输出：2
// 
// 示例 4：
// 输入：A = "aabc", B = "abca"
//输出：2 
//
//
// 提示： 
// 1 <= A.length == B.length <= 20
// A 和 B 只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母。 
// 
// Related Topics 广度优先搜索 图 
// 👍 81 👎 0

import java.util.Arrays;

public class KSimilarStrings854 {
    public static void main(String[] args) {
        Solution solution = new KSimilarStrings854().new Solution();
        System.out.println(solution.kSimilarity("bccaba", "abacbc")); // 3
        System.out.println(solution.kSimilarity("abccaacceecdeea", "bcaacceeccdeaae")); // 9
        System.out.println(solution.kSimilarity("abcdeabcdeabcdeabcde", "aaaabbbbccccddddeeee")); // 8
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        class DisjointSet {
            int count;
            int[] parent;
            public DisjointSet(int n) {
                parent = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                }
            }
            public int find(int i) {
                while (parent[i] != i) {
                    parent[i] = parent[parent[i]];
                    i = parent[i];
                }
                return parent[i];
            }
            public void union (int a, int b) {
                int aRoot = find(a);
                int bRoot = find(b);
                if (aRoot != bRoot) {
                    parent[bRoot] = aRoot;
                    count++;
                }
            }
            public int getCount() {
                return count;
            }
        }
        public void replaceRepeatWord(char[] chars, int n) {
            int[] count = new int[6];
            for (int i = 0; i < 6; i++) {
                count[i] = -1;
            }
            for (int i = 0; i < n; i++) {
                count[chars[i] - 'a']++;
            }
            int[] start = new int[6];
            int preSum = 0;
            for (int i = 0; i < 6; i++) {
                start[i] = preSum;
                preSum += count[i];
            }
            for (int i = 0; i < n; i++) {
                int index = chars[i] - 'a';
                if (count[index] != 0) {
                    chars[i] = (char)('z' - start[index] - count[index]);
                    count[index]--;
                }
            }
        }
        public int kSimilarity(String A, String B) {
            DisjointSet disjointSet = new DisjointSet(25);
            char[] arrayA = A.toCharArray();
            char[] arrayB = B.toCharArray();
            int n = arrayA.length;
            replaceRepeatWord(arrayA, n);
            replaceRepeatWord(arrayB, n);
            System.out.println(Arrays.toString(arrayA));
            System.out.println(Arrays.toString(arrayB));
            for (int i = 0; i < n; i++) {
                disjointSet.union(arrayA[i] - 'a', arrayB[i] - 'a');
            }
            return disjointSet.getCount();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}